/* 
为了实现前缀树（Trie），我们需要设计一个树形结构，其中每个节点代表一个字符，并通过子节点连接形成字符串。
每个节点包含两个核心属性：一个存储子节点的映射和一个标记该节点是否为某个单词的结尾。

方法思路
节点结构：每个节点包含一个对象 children 用于存储子节点，以及一个布尔值 isEnd 标记该节点是否为单词的结尾。
插入操作：从根节点开始，遍历单词的每个字符，为每个字符创建对应的子节点（如果不存在），并在单词结束时标记最后一个节点。
搜索操作：从根节点开始，检查每个字符对应的子节点是否存在。如果所有字符都存在且最后一个字符的节点被标记为结尾，则返回 true。
前缀检查：与搜索操作类似，但只需检查所有字符是否存在，无需验证结尾标记。
*/
var Trie = function () {
  this.root = new TrieNode();
};

class TrieNode {
  constructor() {
    this.children = {}; // 存储子节点的映射
    this.isEnd = false; // 标记是否为单词结尾
  }
}

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
  let current = this.root;
  for (const char of word) {
    if (!current.children[char]) {
      current.children[char] = new TrieNode();
    }
    current = current.children[char];
  }
  current.isEnd = true; // 标记单词结束
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
  let current = this.root;
  for (const char of word) {
    if (!current.children[char]) {
      return false;
    }
    current = current.children[char];
  }
  return current.isEnd; // 必须是完整单词
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
  let current = this.root;
  for (const char of prefix) {
    if (!current.children[char]) {
      return false;
    }
    current = current.children[char];
  }
  return true; // 只需存在前缀路径
};